package dfs;

public class NumberOfIslands_200 {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 每发现一个岛屿，岛屿数量加1，由于将一个岛屿周围的岛屿都变成0，所以一个岛屿只能算上一次
                    res++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return res;
    }

    /**
     *
     * @param grid
     * @param i 当前行
     * @param j 当前列
     * @param m 最大行
     * @param n 最大列
     */
    private void dfs(char[][] grid, int i, int j, int m, int n) {
        // 边界检测
        if (i >= m || i < 0 || j >= n || j < 0) {
            return;
        }

        // 已经是海水了，尽管在numIslands中已经判断为1，但是递归调用中还是可能为0
        if (grid[i][j] == '0') {
            return;
        }
        // 将已经遍历过的岛屿变成0，这样下次遍历就会直接return
        grid[i][j] = '0';

        // 开始遍历周围的岛屿，将周围的岛屿也变为0
        dfs(grid, i+1, j, m ,n);
        dfs(grid, i-1, j, m ,n);
        dfs(grid, i, j-1, m ,n);
        dfs(grid, i, j+1, m ,n);
    }
}
